package 题目集.线段树or树状数组.树状数组;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

/**
 * https://www.acwing.com/problem/content/790/
 * 动态构建一个数值频率表，求某个数的逆序对时，就是0~该数之间所有词频之和。
 * 所以我们可以通过一个树状数组，动态的维护这个频率表，并动态求前缀和。
 * 归并相对于这种方式，归并是静态的求所有的逆序对数量（离线）。这种方式时动态求逆序对数量。
 */
public class ch03_逆序对 {
    static int[] origin;
    static int n;
    static int maxH = 1000010;
    static int[] tree;

    public static void main(String[] args) {
        Reader sc = new Reader(System.in);
        n = sc.nextInt();
        origin = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            origin[i] = sc.nextInt();
        }
        //离散化
        agge(origin);
        long res = 0;
        tree = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            add(origin[i], 1);
            res += range(origin[i] + 1, n);
        }
        System.out.println(res);
    }

    public static void add(int i, int v) {
        while (i <= n) {
            tree[i] += v;
            i += lowbit(i);
        }
    }

    public static int range(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    public static int sum(int i) {
        int res = 0;
        while (i > 0) {
            res += tree[i];
            i -= lowbit(i);
        }
        return res;
    }

    public static int lowbit(int x) {
        return x & -x;
    }

    /**
     * 对数组arr，进行离散化
     */
    public static void agge(int[] arr) {
        int[] sort = arr.clone();
        Arrays.sort(sort);
        int n = quChong(sort);
        for (int i = 1; i < arr.length; i++) {
            arr[i] = rank(sort, 1, n, arr[i]);
        }
    }

    /**
     * 去重，并返回不重复的个数
     * @return
     */
    public static int quChong(int[] sort) {
        int size = 0;
        for (int i = 1; i < sort.length; i++) {
            if (sort[size] != sort[i]) {
                sort[++size] = sort[i];
            }
        }
        return size;
    }

    public static int rank(int[] sort, int l, int r, int v) {
        while (l <= r) {
            int m = l + r >> 1;
            if (sort[m] == v) return m;
            if (v < sort[m]) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }

    static class Reader {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public Reader(Object... o) {
        }

        public static int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }
    }
}
